#ifndef SORT_H
#define	SORT_H

#include "list.h"
#include "utils.h"

template<typename List1, typename List2>
struct Merge
{
   typedef typename MetaIf<(List1::data) < (List2::data),
           List<List1::data, typename Merge<typename List1::tail, List2>::result >,
           List<List2::data, typename Merge<List1, typename List2::tail>::result > >::result result;
};

template<typename List1>
struct Merge<List1, EmptyList>
{
   typedef List1 result;
};

template<typename List2>
struct Merge<EmptyList, List2>
{
   typedef List2 result;
};

template<typename list>
struct Sort
{
   typedef typename Merge< typename Sort< typename Prefix< Length<list>::length / 2, list >::result >::result,
           typename Sort< typename Suffix< Length<list>::length / 2, list >::result >::result >::result result;
};

template<>
struct Sort<EmptyList>
{
   typedef EmptyList result;
};

template<int value>
struct Sort<List<value, EmptyList> >
{
   typedef List<value, EmptyList> result;
};

#endif